#
# @lc app=leetcode.cn id=134 lang=python
#
# [134] 加油站
#

# @lc code=start
class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        total_gas = 0
        sum_gas = 0
        start_index = 0
        i = 0
        for i in range(len(gas)):
            sum_gas += gas[i]- cost[i]
            total_gas += gas[i] - cost[i]
            if sum_gas < 0:
                start_index = i+1
                sum_gas = 0

        if total_gas < 0:
            return -1
        return start_index
        
# @lc code=end
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
print(Solution().canCompleteCircuit(gas, cost)) # 3
